The automatic switched optical network (ASON) is an optical transmission technology with intelligent characteristics. It utilizes standard protocols, such as signaling, routing, automatic discovery, etc., to implement functions, such as routing automatic calculation, connection automatic setup, network source automatic discovery, etc., to improve the automatic control ability of the optical transmission network such that the optical transmission network has intelligent characteristics like the IP network. A route controller, which acts as a module in charge of routing automatic calculation, is an important component module of a control plane of the ASON, and is also an important embodiment of its intellectualization.
The route controller in the ASON usually obtains a shortest path using the traditional open shortest path first (OSPF) protocol. However, in some cases, it is not enough to provide only one path. For example, the resource matching problem may be involved in some applications. If the matching is unsuccessful, indicating that this path is obstructed, then routing calculation from a source node to a destination node will be failed. Therefore, in some applications of the ASON, the K shortest paths (KSP) algorithm is used to solve the resource matching problem. That is, K shortest alternative paths will be calculated by the route controller to provide a condition that the resource matching can determine a resource constrained shortest path among all the K alternative paths. Therefore, where K shortest alternative paths are required to be calculated, the KSP algorithm is an important function in the route controller.
As shown in FIG. 1, there are two processing modules in the route controller of the ASON, one being a resource matching (RM) module which mainly provides the resource matching function, the other being a KSP module configured to receive a route query request, calculate routes and send the calculated routes to the RM module, which processes the resource matching. The work procedure of the processing modules in the route controller of the ASON is shown in FIG. 2, and comprises the following steps. In step 10, the KSP module receives a route query request from a source node to a destination node. In step 11, the KSP module calculates the K routes and returns them to the RM module. In step 12, the RM module performs the resource matching on the K received routes. In step 13, the RM module returns the matching result to a query initiator. According to such a work mode, the KSP module stops calculation only if the K shortest alternative paths have been calculated completely, or there is no other alternative route available in the network even if the K shortest alternative paths have not been calculated yet completely. Then, the KSP module sends all the calculated paths to the RM module for resource matching.
At present there are many research literatures on the KSP algorithm, and the KSP algorithm used for calculating K routes is relatively mature. Whichever scheme the KSP algorithm uses, the time complexity of the whole KSP algorithm is directly proportional to the value of K. The value of K, which is a main parameter of the KSP algorithm, is preset. If the value of K is set to be too small, then the number of the obtained alternative routes is relatively small, and it is possible that a route meeting the resource matching requirement can not be found in the routes; if the value of K is set to be too large, then the KSP algorithm consumes longer time. It can be seen that there is contradiction between reduction of consumed time of the KSP algorithm and satisfaction of the resource matching requirement when the route is determined.
Content of the Invention
The present invention provides a method and device for determining a route so as to solve the problem that there is a there is contradiction between reduction of consumed time of the KSP algorithm and satisfaction of the resource matching requirement in the prior art.
In order to solve the above problem, the present invention provides the following technical scheme.
The present invention provides a method for determining a route comprising:
presetting the number N of routes, performing a K shortest paths algorithm after a route query request is received, calculating the routes by group according to the number N of the routes, whenever N routes are calculated, outputting the N calculated routes as a group, and assigning resources to the group of routes; and
stopping calculating the routes if a route on which resource matching is successful is obtained from the group of routes, and using the route on which the resource matching is successful as the determined route; otherwise, performing the resource matching on the next group of output routes to determine a route;
where N is a positive integer and 1<N<K.
The method further comprises: determining whether all routes have been calculated completely, and stopping the K shortest paths calculation procedure when all routes have been calculated completely.
The method further comprises: determining whether all routes have been calculated and matched completely when the resource matching is unsuccessful, and terminating the route determining procedure when all routes have been calculated and matched completely.
The routes are calculated in an order of path quality from good to poor; and the resource matching is performed in an order of path quality from good to poor in the group of routes.
N is 2, 3, 4 or 5.
The present invention further provides a device for determining a route comprising:
a route calculation module configured to preset the number N of routes, perform a K shortest paths algorithm after a route query request is received, calculate the routes by group according to the number N of the routes, whenever N routes are calculated, output the N calculated routes as a group to a resource matching module, and perform resource matching on the group of routes; and
the resource matching module configured to perform the resource matching on the group of received routes, if a route on which the resource matching is successful is obtained, use the route as the determined route and notify the route calculation module to stop calculating the routes; otherwise, perform the resource matching on the next group of received routes to determine a route;
where N is a positive integer and 1<N<K.
The route calculation module is further configured to determine whether all routes have been calculated completely, and stop the K shortest paths calculation procedure when all routes have been calculated completely.
The resource matching module is further configured to determine whether all routes have been calculated and matched completely when the resource matching is unsuccessful, and terminating the route determining procedure when all routes have been calculated and matched completely.
The route calculation module calculates the routes in an order of path quality from good to poor; and the resource matching module is further configured to perform the resource matching on the routes output by the route calculation module in an order of path quality from good to poor.
N is 2, 3, 4 or 5.
In the method and device in accordance with the present invention, when the K shortest paths algorithm is performed, after a group of routes the number of which is less than K are obtained, the resource matching is performed on these routes, while the K shortest paths algorithm is continuously performed. If there is a route on which resource matching is successful in the group of routes, then the K shortest paths algorithm can be terminated in advance. Since a suitable value of K can be set to ensure basically that success of the resource matching can be obtained in K alternative paths, the method and device in accordance with the present invention, on one hand, can ensure that the route on which resource matching is successful can be obtained through the K shortest paths algorithm, and on the other hand, can assist the system in exiting the K shortest paths calculation in advance, which is helpful to solve the contradiction between reduction of consumed time of the KSP algorithm and satisfaction of the resource matching requirement, thereby improving the efficiency of determining a route.